\documentclass[12pt,a4paper]{article}
\usepackage{xeCJK}
\usepackage{ctex}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{float}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{color}
\usepackage{bm}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{appendix}
\usepackage{latexsym}%约等号\approx
\usepackage{listings}
\usepackage{amsfonts}%有双竖线的大写字母宏包 \mathbb{}

\setstretch{1.2} 
\setlength{\parindent}{0.8cm}
\geometry{left=3cm,right=3cm,top=2.5cm,bottom=2.5cm}
\title{\vspace{-2cm} \textbf{Theoretical Assignments 2 of Numerical Analysis}}

\author{赵竟廷 3200105665}
\date{October 2022}

\begin{document}
\maketitle

\section{Theoretical Questions \uppercase\expandafter{\romannumeral1}}
\begin{itemize}
    \item $f[x_0]=1,f[x_1]=\frac{1}{2},f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0}=-\frac{1}{2}$.
    
    So ,we have $p_1(f;x)=f[x_0]+f[x_0,x_1](x-x_0)=-\frac{1}{2}x$.
    
    Then we have
    \begin{align}
        f(x)-p_1(f;x)&=\frac{f''(\xi(x))}{2}(x-x_0)(x-x_1)\\
        \frac{1}{x}+\frac{1}{2}x-\frac{3}{2}&=\frac{1}{(\xi(x))^3}(x-1)(x-2)
    \end{align}
    By the formula above we can know that 
    \begin{equation}
        \xi(x)=\sqrt[3]{2x}
    \end{equation}

    \item When extend $(x_1,x_2)$to$[x_1,x_2]$,  $\xi(x)=\sqrt[3]{2}x^{\frac{1}{3}},x\in [1,2]$, and we know that $\xi(x)$ is a monotone increasing function. So we have
    \begin{align}
        max\;\xi(x)=\xi(2)=\sqrt[3]{4}\\
        min\;\xi(x)=\xi(1)=\sqrt[3]{2}
    \end{align}
    Since $f''(\xi(x))=f''(\sqrt[3]{2x})=\frac{1}{x}$, we know that $f''(\xi(x))$ is a monotone decreasing function. Then we have
    \begin{equation}
        max\;f''(\xi(x))=f''(\xi(1))=1.
    \end{equation}
\end{itemize}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral2}}

Suppose there is a $g(x_i)$, which satisfies $p(x_i)=[g(x_i)]^2$. That means 
\begin{equation}
    p(x_i)=[g(x_i)]^2=f_i \quad \quad(p \in \mathbb{P}_{2n}^+\: , \:i=0,1,\dots,n)
\end{equation}
By the formula above , we can know that $g(x_i)=\sqrt{f_i}$.
Then we have
\begin{equation}
    g(x)=\sum_{k=0}^ng_k\,l_k(x)=\sum_{k=0}^n(\sqrt{f_k}\prod_{i\neq k,i=0}^n\frac{x-x_i}{x_k-x_i}).
\end{equation}

Then we can get 
\begin{equation}
    p(x)=[g(x)]^2=[\sum_{k=0}^n(\sqrt{f_k}\prod_{i\neq k,i=0}^n\frac{x-x_i}{x_k-x_i})]^2.
\end{equation}


\section{Theoretical Questions \uppercase\expandafter{\romannumeral3}}
\begin{itemize}
    \item By induction, we have following results.
    If $n=0$,$f[t]=e^t$.
    Suppose that when $n=k$:
    \begin{equation}
        f[t,t+1,\dots,t+k]=\frac{(e-1)^k}{k!}e^t
        \label{111}
    \end{equation}
    When $n=k+1$,let $u=t+1$,thus by equation \ref{111} ,we have :
    \begin{equation}
        f[u,u+1,\dots,u+k]=\frac{(e-1)^k}{k!}e^u
    \end{equation}
    which means:
    \begin{equation}
        f[t+1,t+2,\dots,t+k+1]=\frac{(e-1)^k}{k!}e^(t+1)
    \end{equation}
    By theorem 2.17,we have:
    \begin{align}
        f[t,t+1,\dots,t+k,t+k+1]
        &=\frac{f[t+1,t+2,\dots,t+k+1]-f[t,t+1,\dots,t+k]}{(t+k+1)-t}\nonumber\\
        &=\frac{1}{k+1}[\frac{(e-1)^k}{k!}e^{t+1}-\frac{(e-1)^k}{k!}e^t]\nonumber\\
        &=\frac{(e-1)^ke^t(e-1)}{(k+1)!}\nonumber\\
        &=\frac{(e-1)^{k+1}}{(k+1)!}e^t
    \end{align}
    By induction,we know that $f[t,t+1,\dots,t+n]=\frac{(e-1)^n}{n!}e^t$.

    \item From the equations above ,we know that $f[0,1,\dots,n]=\frac{(e-1)^n}{n!}$.

    Since $f(x)=e^x$, we know that $f^{(n)}(\xi)=e^\xi$.

    So,$e^\xi=(e-1)^n$,then we have $\xi=n\,ln(e-1)$.
    To know the location of $\xi$, we consider the following formula .
    \begin{align}
        \xi-\frac{n}{2}
        &=n\,ln(e-1)-\frac{n}{2}\nonumber\\
        &=n[ln(e-1)-\frac{1}{2}]\nonumber\\
        &=n[ln(e-1)-ln\sqrt{e}]\nonumber\\
        &=n\;ln\frac{e-1}{\sqrt{e}}\nonumber\\
        &>0.
    \end{align}
    So $\xi$ is located to  the right of  the midpoint $\frac{n}{2}$.
\end{itemize}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral4}}
\begin{itemize}
    \item By Newton formula we know that $p_3(f;x)=\sum_{k=0}^n a_k \Pi_k(x)$.
    \begin{align}
        a_0&=f[x_0]=f(x_0)=5\\
        a_1&=f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0}=\frac{3-5}{1-0}=-2\\
        a_2&=f[x_0,x_1,x_2]=\sum_{i=0}^2\frac{f_i}{\Pi_{j\neq i,j = 0}^k(x_i-x_j)}=1\\
        a_3&=f[x_0,x_1,x_2,x_3]=\sum_{i=0}^3\frac{f_i}{\Pi_{j\neq i,j = 0}^k(x_i-x_j)}=\frac{1}{4}
    \end{align}
    Then we have:
    \begin{align}
        p_3(f;x)
        &=\sum_{k=0}^3 a_k \Pi_k(x)\nonumber\\
        &=\frac{1}{4}x^3-\frac{9}{4}x+5
    \end{align}

    \item Suppose $\frac{1}{4}x^3-\frac{9}{4}x+5$, then $g'(x)=\frac{3}{4}x^2-\frac{9}{4}$.
    From the formula we know that $g(x)$ is monotonically decreasing at $(1,\sqrt{3})$ and is monotonically increasing at $(\sqrt{3},3)$.So $g(x)$ has a minimum at $x=\sqrt{3}$. So $\bm{\sqrt{3}}$ is an approximate value for the location $x_{min}$.

\end{itemize}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral5}}
\begin{itemize}
    \item The table of divided differences :

\begin{tabular}{c|cccccc}
0 & 0\\ 
1 & 1 & 1\\
1 & 1 & 7 & 6\\
1 & 1 & 7 & 21 & 15\\
2 & 128 & 127 & 120 & 99 & 42\\
2 & 128 & 448 & 321 & 201 & 102 & 30\\
\end{tabular}

So $f[0,1,1,1,2,2]=30$.

\item Since $f(x)=x^7$, we have $f^{(5)}(x)=2520x^2$.
Then we have the following formula:
\begin{equation}
    f[0,1,1,1,2,2]=\frac{1}{5!}f^{(5)}(\xi)=21\xi^2=30\quad(\xi\in(0,2))
\end{equation}
Solve the formula we can know that $\bm{\xi=\sqrt{\frac{10}{7}}}$.
\end{itemize}


\section{Theoretical Questions \uppercase\expandafter{\romannumeral6}}
\begin{itemize}
    \item The table of divided differences :

\begin{tabular}{c|ccccc}
0 & 1\\ 
1 & 2 & 1\\
1 & 2 & -1 & -2\\
3 & 0 & -1 & 0 & $\frac{2}{3}$\\
3 & 0 & 0 & $\frac{1}{2}$ & $\frac{1}{4}$ & $-\frac{5}{36}$\\
\end{tabular}

Then we have 
\begin{equation}
    p_4(f;x)=-\frac{5}{36}x^4+\frac{49}{36}x^3-\frac{155}{36}x^2+\frac{49}{12}x+1
\end{equation}
So,$f(2)\approx p_4(f;2)=\frac{11}{18}$.

\item Estimate the maximum possible error by Cauchy remainder.Since $f \in \mathcal{C}^5[0,3]$ and $|f^{(5)}(x)|\leq M $ on $[0,3]$, we have
\begin{align}
    error&=|R_4(f;2)|\\
    &=|\frac{f^{(5)}(2)}{5!}(2-0)(2-1)^2(2-3)^2|\\
    &\leq \frac{M}{5!}·2\\
    &\leq \frac{M}{60}
\end{align}
    So the maximum possible error is $\frac{M}{60}$.
\end{itemize}



\section{Theoretical Questions \uppercase\expandafter{\romannumeral7}}

Use induction to prove this question.When $k=1$, we have
\begin{equation}
    \Delta f(x)=f(x+h)-f(x)=f(x_1)-f(x_0)=(x_1-x_0)f[x_0,x_1]=hf[x_0,x_1].
\end{equation}
Suppose that when $k=n$,the formula holds. Then we have:
\begin{equation}
    \Delta^nf(x)=n!h^nf[x_0,x_1,\dots,x_n].
\end{equation}
When $k=n+1$, by theorem 2.17, we have
\begin{align}
    \Delta^{n+1}f(x)&=\Delta^nf(x+h)-\Delta^nf(x)\nonumber\\
    &=n!h^nf[x_0+h,x_1+h,\dots,x_n+h]-n!h^nf[x_0,x_1,\dots,x_n]\nonumber\\
    &=n!h^n(f[x_1,x_2,\dots,x_{n+1}]-f[x_0,x_1,\dots,x_n])\nonumber\\
    &=n!h^n(x_{n+1}-x_0)f[x_0,x_1,\dots,x_{n+1}]\nonumber\\
    &=n!h^n(n+1)hf[x_0,x_1,\dots,x_{n+1}]\nonumber\\
    &=(n+1)!h^{n+1}f[x_0,x_1,\dots,x_{n+1}].
\end{align}
Then by the same way, we can prove the other formula.\\
When $k=1$, we have
\begin{equation}
    \nabla f(x)=f(x)-f(x-h)=f(x_0)-f(x_{-1})==hf[x_0,x_{-1}].
\end{equation}
Suppose that when $k=n$,the formula holds. Then we have:
\begin{equation}
    \nabla^nf(x)=n!h^nf[x_0,x_{-1},\dots,x_{-n}].
\end{equation}
When $k=n+1$, we have
\begin{align}
    \nabla^{n+1}f(x)&=\nabla^nf(x)-\nabla^nf(x-h)\nonumber\\
    &=n!h^n(f[x_0,x_1,\dots,x_n]-f[x_{-1},x_{-2},\dots,x_{-n-1}])\nonumber\\
    &=n!h^n(x_0-x_{-n-1})f[x_0,x_{-1},\dots,x_{-n-1}]\nonumber\\
    &=(n+1)!h^{n+1}f[x_0,x_{-1},\dots,x_{-n-1}].
\end{align}
q.e.d

\section{Theoretical Questions \uppercase\expandafter{\romannumeral8}}
According to the definition of partial derivative，we can get the following formula
\begin{equation}
    \frac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_n]=\lim_{\Delta x \to 0}\frac{f[x_0+\Delta x,x_1,\dots,x_n]-f[x_0,x_1,\dots,x_n]}{\Delta x}.
\end{equation}

By Corollary 2.15, we can transform the formula to get the result.
\begin{align}
    \frac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_n]
    &=\lim_{\Delta x \to 0}\frac{f[x_1,\dots,x_n,x_0+\Delta x]-f[x_0,x_1,\dots,x_n]}{(x_0+\Delta x)-x_0}\nonumber\\
    &=\lim_{\Delta x \to 0}f[x_0,x_1,\dots,x_n,x_0+\Delta x]\\
    &=f[x_0,x_1,\dots,x_n,x_0]\nonumber\\
    &=f[x_0,x_0,x_1,\dots,x_n]\nonumber
\end{align}

For one of the other variables $x_i\;(i=1,2,\dots,n)$, we can calculate the partial derivative by following formulas.
\begin{align}
    &\frac{\partial}{\partial x_i}f[x_0,x_1,\dots,x_n]\nonumber\\
    &=\lim_{\Delta x \to 0}\frac{f[x_0,x_1,\dots,x_i+\Delta x,\dots,x_n]-f[x_0,x_1,\dots,x_i,\dots,x_n]}{\Delta x}\nonumber\\
    &=\lim_{\Delta x \to 0}\frac{f[x_0,\dots,x_{i-1},x_{i+1},\dots,x_n,x_i+\Delta x]-f[x_i,x_0,\dots,x_{i-1},x_{i+1},\dots,x_n]}{(x_i+\Delta x)-x_i}\nonumber\\
    &=\lim_{\Delta x \to 0}f[x_i,x_0,\dots,x_{i-1},x_{i+1},\dots,x_n,x_i+\Delta]\\
    &=f[x_0,\dots,x_{i-1},x_i,x_i,x_{i+1},\dots,x_n]\nonumber
\end{align}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral9}}
Let $f(x)=a_0x^n+a_1x^{n-1}+\dots+a_n$.

Since $a_0\neq0$ , let
\begin{align}
    p(x)=x^n+\frac{a_1}{a_0}x^{n-1}+\dots+\frac{a_n}{a_0}=x^n+a_1'x^{n-1}+\dots+a_n'.
\end{align}

Since $x\in[a,b]$, let $x=\frac{b-a}{2}y+\frac{a+b}{2}\:(y\in[-1,1])$.

Then we have
\begin{align}
    p(y)&=(\frac{b-a}{2}y+\frac{a+b}{2})^n+a_1'(\frac{b-a}{2}y+\frac{a+b}{2})^{n-1}+\dots+a_n'\\
    &=(\frac{b-a}{2})^n(y^n+b_1y^{n-1}+\dots+b_n)
\end{align}
where $b_i\;(i=1,2,\dots,n)$ is related to $a,b,a_i'$.

Let $g(y)=y^n+b_1y^{n-1}+\dots+b_n\:(y\in[-1,1])$. Then by corollary 2.45, we know that 
\begin{equation}
    \max_{y\in[-1,1]}|g(y)|\ge \frac{1}{2^{n-1}}
\end{equation}

Thus $\max_{y\in[-1,1]}p(y)\ge (\frac{b-a}{2})^n\frac{1}{2^{n-1}}$.Since variable replacement has no effect on the extremum of functions, we have
\begin{equation}
    \max_{x\in[a,b]}|p(x)|\ge |(\frac{b-a}{2})^n|\frac{1}{2^{n-1}}
\end{equation}
Thus we have
\begin{equation}
    min\:\max_{x\in[a,b]}|f(x)|=|a_0||(\frac{b-a}{2})^n|\frac{1}{2^{n-1}}.
\end{equation}
which means $min\:\max_{x\in[a,b]}|a_0x^n+a_1x^{n-1}+\dots+a_n|=|a_0(\frac{b-a}{2})^n|\frac{1}{2^{n-1}}$.

\section{Theoretical Questions \uppercase\expandafter{\romannumeral10}}
 By Theorem 2.42, $T_n(x)$ assumes its extrema $n+1$ times at the points $x_k'$ defined by $x_k'=cos\frac{k}{n}\pi \:(k=0,1,\dots,n)$.Suppose the conclusion does
not hold. Then we have
\begin{equation}
    \exists p \in \mathbb{P}_n^a,\quad \lVert \hat{p}_n \rVert_\infty \ge \lVert p \rVert_\infty
\end{equation}
which means
\begin{equation}
    \exists p \in \mathbb{P}_n^a,\: s.t. \: \max_{x\in[-1,1]} |p(x)| < \frac{1}{|T_n(a)|}
    \label{2.46}
\end{equation}

Consider the polynomial $Q(x)=\frac{1}{|T_n(a)|}-p(x)$.
\begin{equation}
    Q(x_k')=\frac{(-1)^k}{T_n(a)}-p(x_k'),\quad k=0,1,\dots,n.
\end{equation}
By (\ref{2.46}), $Q(x)$ has alternating signs at these n+1 points. Hence $Q(x)$ must have $n$ zeros. However, by the construction of $Q(x)$, the degree of $Q(x)$ is at most $n-1$. Therefore, $Q(x)\equiv 0$ and $p(x)=\frac{1}{T_n(a)}T_n(x)$,which implies $max |p(x)|=\frac{1}{T_n(a)}$. This is a contradiction to (\ref{2.46}).

So,$\forall p \in \mathbb{P}_n^a,\quad \lVert \hat{p}_n \rVert_\infty \leq \lVert p \rVert_\infty$.

\section{Theoretical Questions \uppercase\expandafter{\romannumeral11}}
\begin{itemize}
    \item Prove: $\bm{b_{n,k}(t)>0}$

    Since $t\in(0,1)$, we have $t>0,(1-t)>0$. So we can know that $t^k>0,(1-t)^{n-k}>0$. Thus $b_{n,k}(t)>0$.

    \item Prove :$\bm{\sum_{k=0}^nb_{n,k}(t)=1}$

    By binomial theorem ，we have
    \begin{equation}
        \sum_{k=0}^nb_{n,k}(t)=\sum_{k=0}^n C_n^k t^k (1-t)^{n-k}=[t+(1-t)]^n=1
    \end{equation}

    \item Prove: $\bm{\sum_{k=0}^n kb_{n,k}(t)=nt}$

    By binomial theorem ，we have
    \begin{align}
        \sum_{k=0}^n kb_{n,k}(t)
        &=\sum_{k=0}^n C_n^k k t^k (1-t)^{n-k}\nonumber\\
        &=\sum_{k=0}^n \frac{n\dots(n-k+1)}{k!}k t^k(1-t)^{n-k}\nonumber\\
        &=0+\sum_{k=1}^n n \frac{(n-1)\dots((n-1)-(k-1)+1)}{(k-1)!}t^k(1-t)^{n-k}\nonumber\\
        &=\sum_{k=1}^n n C_{n-1}^{k-1} t·t^{k-1}(1-t)^{[(n-1)-(k-1)]}\\
        &=\sum_{k=1}^n nt C_{n-1}^{k-1} t^{k-1} (1-t)^{[(n-1)-(k-1)]}\nonumber\\
        &=nt[t+(1-t)]^{n-1}\nonumber\\
        &=nt\nonumber
    \end{align}

    \item Prove: $\bm{\sum_{k=0}^n (k-nt)^2 b_{n,k}(t)=nt(1-t)}$

    We have:
    \begin{align}
        \sum_{k=0}^n (k-nt)^2 b_{n,k}(t)
        &=\sum_{k=0}^n k^2 b_{n,k}(t) -2nt \sum_{k=0}^n k b_{n,k}(t) + n^2 t^2 \sum_{k=0}^n b_{n,k}(t)\nonumber\\
        &=\sum_{k=0}^n k^2 b_{n,k}(t) - 2n^2 t^2 + n^2 t^2\\
        &=\sum_{k=0}^n k^2 b_{n,k}(t) - n^2 t^2\nonumber
    \end{align}

    So we want to calculate $\sum_{k=0}^n k^2 b_{n,k}(t)$ to prove the formula.
     By what we have proved before, we can get following formulas.

     \begin{align}
         \sum_{k=0}^n k^2 b_{n,k}(t)
         &=\sum_{k=0}^n k^2 C_n^k t^k (1-t)^{n-k}\nonumber\\
         &=\sum_{k=0}^n k^2\frac{n\dots (n-k+1)}{k!} t^k (1-t)^{n-k}\nonumber\\
         &=\sum_{k=1}^n k \frac{n(n-1)\dots (n-k+1)}{(k-1)!}t^k (1-t)^{n-k}\nonumber\\
         &=nt \sum_{k=1}^n k C_{n-1}^{k-1}t^{k-1}(1-t)^{[(n-1)-(k-1)]}\\
         &=nt[\sum_{k=1}^n(k-1) C_{n-1}^{k-1}t^{k-1}(1-t)^{n-k}+\sum_{k=1}^n C_{n-1}^{k-1}t^{k-1}(1-t)^{n-k}]\nonumber\\
         &=nt[(n-1)t+1]\nonumber\\
         &=n^2t^2-nt^2+nt\nonumber
     \end{align}
     So we have 
     \begin{align}   
         \sum_{k=0}^n (k-nt)^2 b_{n,k}(t)
         &=\sum_{k=0}^n k^2 b_{n,k}(t) - n^2 t^2\nonumber\\
         &=n^2t^2-nt^2+nt-n^2 t^2\\
         &=nt(1-t)\nonumber
     \end{align}

     q.e.d
\end{itemize}


\end{document}
